Abstract Despite the known benefits, most individuals do not achieve the recommended levels of physical activity (PA). Overall, African American women have the lowest PA levels, which contributes to substantial disparities in cardiovascular health, diabetes, and depressive symptoms. There is a pressing need to examine ways to promote PA in African American women that are appealing, applicable to clinical practice, and cost-effective. The purpose of this clinical trial is to test the efficacy of our reframed Women's Walking Program (WWP), consisting of a lifestyle PA prescription and group visit delivery model, with or without tailored telephone contacts between group visits for increasing adherence to PA and improving health outcomes. Two telephone contact strategies will be compared against a no-telephone control condition: a person-administered contact strategy using brief motivational interviewing and an automated contact strategy using a telephone computer- linked system. Group visits and telephone contacts are designed to increase adherence to lifestyle PA with an emphasis on accumulation of 3,000 steps daily over baseline. The aims of this study are (1) to compare the initial (adoption 24 weeks) and longer-term (maintenance 2nd 24 weeks) effectiveness of the WWP plus person-administered telephone contacts, WWP plus automated telephone contacts, and the WWP without telephone contacts on (a) increasing adherence to lifestyle PA, (b) improving health outcomes (aerobic fitness, body composition, depressive symptoms), (c) improving self-efficacy and outcome expectations; and (2) to compare cost-effectiveness of the three telephone treatment conditions in relation to adherence to lifestyle PA and health outcomes. The study is a randomized cluster Latin Squares clinical trial with random assignment of the order of administering the three treatment conditions to six community health care centers. These six centers are similar with respect to race, socioeconomic status, and residential mobility. African American women (n = 288) aged 40 to 65 years, who are sedentary with no major signs or symptoms of cardiovascular disease and no history of myocardial infarction, stroke, or insulin-dependent diabetes will be recruited within a 3-mile radius of the community health care centers. Data will be collected at baseline, and at 24 weeks and 48 weeks using multiple measures of PA; aerobic fitness testing; BMI; waist circumference; depressive symptoms; self-efficacy for overcoming barriers; and outcome expectations. We anticipate that (a) adherence to lifestyle PA and therefore health outcomes will improve and self-efficacy and outcome expectations will be higher in the WWP complemented with telephone contacts compared to the WWP without telephone contacts and (b) the WWP plus automated telephone contact will be more cost-effective than WWP plus person-administered telephone contacts. This study will contribute to identifying a reimbursable, practical way of delivering a behavioral change intervention in clinical settings that will increase adherence to PA and be attractive and appealing to African American women.